home *** CD-ROM | disk | FTP | other *** search
/ ADA Programming Guide / ADA Programming Guide.iso / ada_gwu / peep.c < prev    next >
C/C++ Source or Header  |  1996-01-30  |  10KB  |  403 lines
  1. /*
  2.  * Copyright (C) 1985-1992  New York University
  3.  * 
  4.  * This file is part of the Ada/Ed-C system.  See the Ada/Ed README file for
  5.  * warranty (none) and distribution info and also the GNU General Public
  6.  * License for more details.
  7.  
  8.  */
  9. #define GEN
  10.  
  11. #include "hdr.h"
  12. #include "vars.h"
  13. #include "gvars.h"
  14. #include "ops.h"
  15. #include "genop.h"
  16. #include "genp.h"
  17. #include "peepp.h"
  18.  
  19. static void code_stack_copy(Op, Op);
  20. static int code_same_arg(Op, Op);
  21. static void flush(int);
  22. static int remov(int);
  23.  
  24. extern int peep_option; /* defined in gmain.c */
  25.  
  26. #define STACK_DEPTH 50
  27. #define MATCH(v) (code_stack[index-1].op_code == v)
  28.  
  29. static Op_s code_stack[STACK_DEPTH + 1]; /* stack of instructions */
  30. static int tos = 0;                         /* top of stack for peep-hole */
  31.  
  32. /*
  33.  *           P E E P - H O L E   O P T I M I Z E R
  34.  *
  35.  * Algorithm: keep a array of instructions to be optimized in the 
  36.  *            global array code_stack. The global variable tos is
  37.  *            the index of the last instruction entered in the array.
  38.  *
  39.  * The algorithm proceeds in three steps:
  40.  *
  41.  * 1/ check if the array is full and take the appropriate action.
  42.  *    Add the new opcode in the array and increment tos.
  43.  *
  44.  * 2/ loop over the list of codes, using the local variable index
  45.  *    as a pointer to the current instruction.
  46.  *
  47.  *    If an optimization is performed, index is set to point to 
  48.  *    the last untouched instruction or to the first instruction
  49.  *    in the array (0 is not used). At the end of the loop, it
  50.  *    is incremented. If an optimization is performed, index may
  51.  *    be decremented by 1 or left untouched. It is incremented
  52.  *    by 1 otherwise. The loop stops when index points to the last
  53.  *    instruction entered in the array. Note: it is essential that
  54.  *    index verifies the following relation on entry of the loop:
  55.  *                       2 <= index < tos
  56.  *    As a consequence, index must be at least 1 on exit of the loop.
  57.  *
  58.  *    If an instruction is garanteed to prevent any further
  59.  *    optimization, all the instructions which preceed are flushed.
  60.  *    This instruction is kept in the array for the shake of the 
  61.  *    'fence post effect'. (I_NOT followed by I_JUMP_IF_FALSE would
  62.  *    not be catched otherwise).
  63.  *
  64.  * 3/ if the last instruction added to the array was I_END, flush
  65.  *    the list and reset tos to 0.
  66.  *
  67.  */
  68.  
  69. void peep_hole(Op next)                                            /*;peep_hole*/
  70. {
  71.     int    index; /* index in the array of instructions: 1 < index < tos */
  72.     Op     temp;  /* temporary op_code */
  73.     char *smalloc();
  74.  
  75.     if (peep_option == 0) { /* if no optimization assemble immediately */
  76.         assemble(next);
  77.         return;
  78.     }
  79.  
  80.     if (tos == 50)
  81.         flush(10);
  82.  
  83.     ++tos;
  84.  
  85.     /* put new instruction in the array */
  86.     code_stack_copy(&code_stack[tos], next);
  87.     for(index = ((tos > 2) ? (tos - 1) : 2); index < tos; index++) {
  88.  
  89.         switch(code_stack[index].op_code) {
  90.  
  91. #ifdef TBSL
  92.         case(I_POP):
  93.             if(MATCH(I_DEREF)) {
  94.                 temp = &code_stack[index-1];
  95.                 temp->op_code = I_INDIRECT_POP;
  96.                 index = remov(index);
  97.             }
  98.             break;
  99.  
  100.         case(I_MOVE):
  101.             if(MATCH(I_DEREF)) {
  102.                 temp = &code_stack[index-1];
  103.                 temp->op_code = I_INDIRECT_MOVE;
  104.                 index = remov(index);
  105.             }
  106.             break;
  107. #endif
  108.  
  109.         case(I_ADD_IMMEDIATE):
  110.             if(MATCH(I_ADD_IMMEDIATE) || MATCH(I_PUSH_IMMEDIATE)) {
  111.                 temp = &code_stack[index-1];
  112.                 temp->op_arg.arg_int = 
  113.                   (temp->op_arg.arg_int + code_stack[index].op_arg.arg_int);
  114.                 index = remov(index);
  115.             }
  116.             /* next is test for integer zero */
  117.             else if (code_stack[index].op_type == OP_INT &&
  118.                 code_stack[index].op_arg.arg_int == 0) {
  119.                 index = remov(index);
  120.             }
  121.             break;
  122.  
  123.         case(I_DEREF):
  124.             if(MATCH(I_PUSH_EFFECTIVE_ADDRESS)) {
  125.                 temp = &code_stack[index-1];
  126.                 temp->op_code = I_PUSH;
  127.                 temp->op_kind = code_stack[index].op_kind;
  128.                 index = remov(index);
  129.             }
  130.             break;
  131.  
  132.         case(I_DISCARD_ADDR):
  133.             if(code_stack[index+1].op_code == I_DISCARD_ADDR) {
  134.                 temp = &code_stack[index];
  135.                 temp->op_kind += code_stack[index+1].op_kind;
  136.                 temp->op_arg.arg_int = temp->op_kind;
  137.                 index = remov(index+1);
  138.             }
  139.             else if(code_stack[index].op_kind == 0) {
  140.                 index = remov(index);
  141.             }
  142.             else if(MATCH(I_PUSH_EFFECTIVE_ADDRESS)) {
  143.                 temp = &code_stack[index];
  144.                 temp->op_kind -= 1;
  145.                 temp->op_arg.arg_int  -= 1;
  146.                 index = remov(index-1);
  147.             }
  148.             else if(MATCH(I_UPDATE)) {
  149.                 temp = &code_stack[index];
  150.                 temp->op_kind -= 1;
  151.                 temp->op_arg.arg_int  -= 1;
  152.                 index -= 1;
  153.                 code_stack[index].op_code = I_UPDATE_AND_DISCARD;
  154.             }
  155.             break;
  156.  
  157.         case(I_FLOAT_POW):
  158.             if(MATCH(I_PUSH_IMMEDIATE)) {
  159.                 temp = &code_stack[index-1];
  160.                 if (temp->op_arg.arg_int == 2) {
  161.                     temp->op_code = I_DUPLICATE;
  162.                     temp->op_kind = code_stack[index].op_kind;
  163.                     code_stack[index].op_code = I_FLOAT_MUL;
  164.                 }
  165.             }
  166.             break;
  167.  
  168.         case(I_PUSH):
  169.             if (MATCH(I_PUSH)
  170.               && (code_same_arg(&code_stack[index], &code_stack[index-1]))) {
  171.                 code_stack[index].op_code = I_DUPLICATE;
  172.             }
  173.             else if(MATCH(I_POP)
  174.               && (code_same_arg(&code_stack[index], &code_stack[index-1]))) {
  175.                 code_stack[index].op_code = I_POP;
  176.                 code_stack[index-1].op_code = I_DUPLICATE;
  177.             }
  178.             break;
  179.  
  180.             case(I_PUSH_EFFECTIVE_ADDRESS):
  181.             if(MATCH(I_UPDATE_AND_DISCARD)
  182.               && (code_same_arg(&code_stack[index], &code_stack[index-1]))) {
  183.                 temp = &code_stack[index-1];
  184.                 temp->op_code = I_UPDATE;
  185.                 index = remov(index);
  186.             }
  187.             break;
  188.  
  189.         case(I_POW):
  190.             if(MATCH(I_PUSH_IMMEDIATE)) {
  191.                 temp = &code_stack[index-1];
  192.                 if (temp->op_type == OP_INT && temp->op_arg.arg_int == 2) {
  193.                     temp->op_code = I_DUPLICATE;
  194.                     temp->op_kind = code_stack[index].op_kind;
  195.                     code_stack[index].op_code = I_MUL;
  196.                 }
  197.             }
  198.             break;
  199.  
  200.         case(I_STMT):
  201.             if (MATCH(I_STMT)) {
  202.                 index = remov(index-1);
  203.             }
  204.             break;
  205.  
  206.         case(I_NOT):
  207.             temp = &code_stack[index+1];
  208.             if(temp->op_code == I_JUMP_IF_FALSE) {
  209.                 temp->op_code = I_JUMP_IF_TRUE;
  210.                 index = remov(index);
  211.             }
  212.             else if(temp->op_code == I_JUMP_IF_TRUE) {
  213.                 temp->op_code = I_JUMP_IF_FALSE;
  214.                 index = remov(index);
  215.             }
  216.             else {
  217.                 flush(index);
  218.                 index = 1;
  219.             }
  220.             break;
  221.  
  222.         /*
  223.          * Here follow the instructions for which no optimization
  224.          * can be attempted. Note: those should not appear in any 
  225.          * of the preceeding rules.
  226.          */
  227.         case(I_ABORT):
  228.         case(I_ABS):
  229.         case(I_ACTIVATE):
  230.         case(I_ACTIVATE_NEW):
  231.         case(I_ADD):
  232.         case(I_AND):
  233.         case(I_ALLOCATE):
  234.         case(I_ALLOCATE_COPY):
  235.         case(I_ARRAY_AND):
  236.         case(I_ARRAY_CATENATE):
  237.         case(I_ARRAY_MOVE):
  238.         case(I_ARRAY_NOT):
  239.         case(I_ARRAY_OR):
  240.         case(I_ARRAY_SLICE):
  241.         case(I_ARRAY_XOR):
  242.         case(I_ATTRIBUTE):
  243.         case(I_CALL):
  244.         case(I_CALL_PREDEF):
  245.         case(I_CASE):
  246.         case(I_CASE_TABLE):
  247.         case(I_COMPARE):
  248.         case(I_COMPARE_STRUC):
  249.         case(I_CONVERT_TO):
  250.         case(I_CREATE):
  251.         case(I_CREATE_COPY):
  252.         case(I_CREATE_COPY_STRUC):
  253.         case(I_CREATE_TASK):
  254.         case(I_CURRENT_TASK):
  255.         case(I_DATA):
  256.         case(I_DECLARE):
  257.         case(I_DIV):
  258.         case(I_END_ACTIVATION):
  259.         case(I_END_FOR_LOOP):
  260.         case(I_END_FORREV_LOOP):
  261.         case(I_END_RENDEZVOUS):
  262.         case(I_ENTER_BLOCK):
  263.         case(I_ENTRY_CALL):
  264.         case(I_FIX_MUL):
  265.         case(I_FIX_DIV):
  266.         case(I_FLOAT_ABS):
  267.         case(I_FLOAT_ADD):
  268.         case(I_FLOAT_COMPARE):
  269.         case(I_FLOAT_DIV):
  270.         case(I_FLOAT_MUL):
  271.         case(I_FLOAT_NEG):
  272.         case(I_FLOAT_SUB):
  273.         case(I_INSTALL_HANDLER):
  274.         case(I_IS_EQUAL):
  275.         case(I_IS_GREATER):
  276.         case(I_IS_GREATER_OR_EQUAL):
  277.         case(I_IS_LESS):
  278.         case(I_IS_LESS_OR_EQUAL):
  279.         case(I_JUMP):
  280.         case(I_JUMP_IF_GREATER):
  281.         case(I_JUMP_IF_GREATER_OR_EQUAL):
  282.         case(I_JUMP_IF_LESS):
  283.         case(I_JUMP_IF_LESS_OR_EQUAL):
  284.         case(I_LABEL):
  285.         case(I_LEAVE_BLOCK):
  286.         case(I_LINK_TASKS_DECLARED):
  287.         case(I_LOAD_EXCEPTION_REGISTER):
  288.         case(I_MEMBERSHIP):
  289.         case(I_MOD):
  290.         case(I_MUL):
  291.         case(I_NEG):
  292.         case(I_NOP):
  293.         case(I_OR):
  294.         case(I_POP_TASKS_DECLARED):
  295.         case(I_QUAL_DISCR):
  296.         case(I_QUAL_INDEX):
  297.         case(I_QUAL_RANGE):
  298.         case(I_QUAL_SUB):
  299.         case(I_RAISE_IN_CALLER):
  300.         case(I_RECORD_MOVE):
  301.         case(I_REM):
  302.         case(I_RESTORE_STACK_POINTER):
  303.         case(I_RETURN):
  304.         case(I_RETURN_STRUC):
  305.         case(I_SAVE_STACK_POINTER):
  306.         case(I_SELECT):
  307.         case(I_SELECTIVE_WAIT):
  308.         case(I_SUB):
  309.         case(I_SUBPROGRAM):
  310.         case(I_SUBSCRIPT):
  311.         case(I_TERMINATE):
  312.         case(I_TEST_EXCEPTION_REGISTER):
  313.         case(I_TIMED_ENTRY_CALL):
  314.         case(I_TYPE_GLOBAL):
  315.         case(I_TYPE_LOCAL):
  316.         case(I_UNCREATE):
  317.         case(I_WAIT):
  318.         case(I_XOR):
  319.         case(I_CALL_INTERFACE):
  320.         case(I_COMPARE_ARRAYS):
  321.         case(I_CHECK_REC_SUBTYPE):
  322.             flush(index-1);
  323.             index = 1;
  324.             break;
  325.  
  326.         default:
  327.             ;
  328.         }
  329.     } /* end for */
  330.  
  331.     if(next->op_code == I_END)
  332.         flush(tos);
  333. }
  334.  
  335. static void code_stack_copy(Op opnew, Op opold)                /*;code_stack_copy*/
  336. {
  337.     /* copy operation values */
  338.     register int i;
  339.     register char *newc, *old;
  340.     old = (char *) opold;
  341.     newc = (char *) opnew;
  342.     for (i = sizeof(Op_s); i; i--)
  343.         *newc++ = *old++;
  344. }
  345.  
  346. static int code_same_arg(Op op1, Op op2)                     /*;code_same_arg*/
  347. {
  348.     /* see if operations i1 and i2 in code_stack have same argument */
  349.     if (op1->op_type != op2->op_type)
  350.         return FALSE;
  351.  
  352.     switch (op1->op_type) {
  353.     case OP_FIX :
  354.         return (op1->op_arg.arg_fix == op2->op_arg.arg_fix);
  355.     case OP_FLT :
  356.         return (op1->op_arg.arg_flt == op2->op_arg.arg_flt);
  357.     case OP_INT :
  358.         return (op1->op_arg.arg_int == op2->op_arg.arg_int);
  359.     case OP_SYM :
  360.         return (op1->op_arg.arg_sym == op2->op_arg.arg_sym);
  361.     }
  362.     return FALSE;
  363. }
  364.  
  365. static void flush(int n)                                             /*;flush*/
  366. {
  367.     /* Flush n instructions from the array code_stack and move
  368.      * the remaining instructions n positions to the beginning
  369.      * of the array. Note: n should be positive. The global 
  370.      * variable tos is set accordingly. If the argument is equal
  371.      * to tos, all the instructions of the array are passed to
  372.      * assemble and tos is set to 0 (peep-hole called with I_END).
  373.      */
  374.  
  375.     int i, j;
  376.  
  377.     for (i = 1; i <= n; i++)
  378.         assemble(&code_stack[i]);
  379.  
  380.     for (j = 1, i = n; i++ < tos; j++)
  381.         code_stack_copy(&code_stack[j], &code_stack[i]);
  382.  
  383.     tos -= n;
  384. }
  385.  
  386. static int remov(int n)                                                /*;remov*/
  387. {
  388.     /*
  389.      * Remove the instruction of rank n from the array.
  390.      * The instructions with greater values of the index, if
  391.      * any, are shifted one position toward the lower indices.
  392.      * This function returns the last untouched index or 1.
  393.      */
  394.  
  395.     int i;
  396.  
  397.     for (i = n; i < tos; i++)
  398.         code_stack_copy(&code_stack[i], &code_stack[i+1]);
  399.  
  400.     tos -= 1;
  401.     return ((n > 1) ? (n-1) : 1);
  402. }
  403.